package com.sx.sx1.lintcode.day717;

import java.util.Arrays;
import java.util.Stack;

public class LC285 {

    static class Solution {
        /**
         * @param arr: the height of all buildings
         * @return: how many buildings can he see at the location of each building
         */
        public int[] tallBuilding(int[] arr) {
            int n = arr.length;
            int[] ans = new int[n];
            Arrays.fill(ans,1);
            Stack<Integer> s= new Stack<>();
            for (int i = 0; i <n ; i++) {
                ans[i]+=s.size();
                while (!s.isEmpty() && arr[s.peek()] <= arr[i]){
                    s.pop();
                }
                s.add(i);
            }
            s.clear();
            for (int i = n-1; i >=0 ; i--) {
                ans[i]+=s.size();
                while (!s.isEmpty() && arr[s.peek()] <= arr[i]){
                    s.pop();
                }
                s.add(i);
            }

            return ans;
        }
    }


    public static void main(String[] args) {
        int[] arr = {5,3,8,3,2,5};
        Solution s = new Solution();
        int[] res = s.tallBuilding(arr);
        for (int re : res) {
            System.out.print(re+" ");
        }

        System.out.println();
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有192条未读消息，请及时查看
285 · 高楼大厦
算法
中等
通过率
58%

题目
题解12
笔记
讨论14
排名
记录
描述
小Q在周末的时候和他的小伙伴来到大城市逛街，一条步行街上有很多高楼，共有n座高楼排成一行，楼高用arr表示。
小Q从第一栋一直走到了最后一栋，小Q从来都没有见到这么多的楼，所以他想知道他在每栋楼的位置处能看到多少栋楼呢？（当前面的楼的高度大于等于后面的楼时，后面的楼将被挡住）

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


1
≤
𝑛
≤
100000
1≤n≤100000
1
≤
𝑎
𝑟
𝑟
[
𝑖
]
≤
100000
1≤arr[i]≤100000

样例
例1:

输入:[5,3,8,3,2,5]
输出:[3,3,5,4,4,4]
解释:
当小Q处于位置0时，他能看到位置0，1，2的3栋高楼。
当小Q位于位置1时，他能看到位置0，1，2的3栋高楼。
当小Q处于位置2时，他可以向前看到位置0，1处的楼，向后看到位置3,5处的楼，加上第3栋楼，共可看到5栋楼。
当小Q处于位置3时，他能看到位置2，3，4，5的4栋高楼。
当小Q处于位置4时，他能看到位置2，3，4，5的4栋高楼。
当小Q处于位置5时，他能看到位置2，3，4，5的4栋高楼。
标签
推荐课程

Twitter 后端系统 - Python 项目实战
从0项目经验到深度后端项目操盘，FB架构师万行代码还原真实开发环境，14周简历镀金
272/1856
已开启智能提示
发起考试
30 分 00 秒
123456789

控制台
        历史提交

 */